package com.链表中倒数第k个节点;

import java.util.Stack;
/*
 * 使用栈是一种方法，但是还有一种更加好的方法
 * 使用两个指针，第一个指针往后走k-1个时候（因为开始的时候在第一个）1 2 3 4 5
 * 第二个指针也开始走，这样就保证两个指针间隔了k-1个然后当第一个指针走到了最后时候
 * 第二个指针就指向了倒数的那个 
 * */
public class Solution {
    public ListNode FindKthToTail(ListNode head,int k) {
       Stack<ListNode> s = new Stack<ListNode>();
        while(head!=null){
            s.push(head);
        }
        if (s.size()<k){
            return null;
        }
        int i = 1;
        ListNode res=null;
        while(i<=k){
            if(i==k){
                res = s.pop();
            }
            else
                s.pop();
            i++;
        }
        return res;
    }
    //此方法就是用了两个指针进行遍历
    public ListNode FindKthToTail1(ListNode head,int k) {
        ListNode first = head;
        ListNode second = head;
        if(head==null||k==0) return null;
        if(head.next==null&&k==1) return head;
        for(int i =1;i<=k-1;i++){
            if(first.next!=null){
            first=first.next;
            }else 
                return null;
        }
        while(first.next!=null){
            first = first.next;
            second = second.next;
        }
        return second;
    }
}
